package backtrackStudy;

import java.util.LinkedList;
import java.util.List;

public class BacktraceStudy10 {

    private static List<List<String>> ans = new LinkedList<>();

    /**
     * LeetCode T131
     * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
     *
     * 回文串 是正着读和反着读都一样的字符串。
     * @param args
     */
    public static void main(String[] args) {

    }

    public static List<List<String>> partition(String s){
        //定义路径记录
        LinkedList<String> trace = new LinkedList<>();
        int len = s.length();
        //通过动态规划，判断子串是否是回文
        boolean[][] dp = new boolean[len][len];
        //进行初始化操作，有些不能够初始化的地方需要填写什么很重要，有些是利用数组初始化的性质，进行隐式初始化
        for (int i = 0; i < len; i++){
            for (int j = 0; j < len; j++){
                dp[i][j] = true;
            }
        }
        //进行动态规划填充数组
        for (int i = len - 1; i >= 0; i--){
            for (int j = i+1; j < len; j++){
                dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1];
            }
        }

        //回溯求值
        backtrace(s, dp, 0, trace);

        return ans;
    }

    //进行回溯，首先确定返回值和参数
    public static void backtrace(String s, boolean[][] dp, int beginIndex, LinkedList<String> trace){
        if (beginIndex == s.length()){
            //记录结果
            ans.add(new LinkedList<>(trace));
            return;
        }
        //循环处理
        for (int j = beginIndex; j < s.length(); j++){
            if (dp[beginIndex][j] == true){
                //选择
                trace.add(s.substring(beginIndex, j + 1));
                //递归处理
                backtrace(s, dp, j + 1, trace);
                //取消选择
                trace.removeLast();
            }
        }
    }
}
